//
// Created by francklinson on 2021/8/25 AT 9:38.
//
//给你一个有n个节点的 有向无环图（DAG），请你找出所有从节点 0到节点 n-1的路径并输出（不要求按特定顺序）
//
//二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
//
//译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。
//
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/all-paths-from-source-to-target
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <functional>
#include <climits>

using namespace std;

class Solution {
public:
    /**
     * 回溯
     * 无环  其实可以不需要seen
     * @param graph
     * @return
     */
    vector<vector<int>> allPathsSourceTarget(vector<vector<int>> &graph) {
        int n = (int) graph.size();
        vector<bool> seen(n, false); // 是否遇见过
        seen[0] = true;
        vector<int> curPath;// 当前走过的路径
        curPath.push_back(0);
        vector<vector<int>> allPaths; // 所有的可行路径集合
        // 回溯函数
        function<void(int)> backtracking = [&](int point) {
            // 找到一条路径
            if (point == n - 1) {
                allPaths.push_back(curPath);
                return;
            }
            for (int &nextPoint : graph[point]) {
                if (!seen[nextPoint]) {
                    // 递归
                    curPath.push_back(nextPoint);
                    seen[nextPoint] = true;
                    backtracking(nextPoint);
                    // 回溯
                    curPath.pop_back();
                    seen[nextPoint] = false;
                }
            }
            return;
        };
        backtracking(0);
        return allPaths;
    }
};

int main() {
    vector<vector<int>> graph{{1, 2},
                              {3},
                              {3},
                              {}};
    vector<vector<int>> g2{{4, 3, 1},
                           {3, 2, 4},
                           {3},
                           {4},
                           {}};
    Solution solution;
    vector<vector<int>> ans = solution.allPathsSourceTarget(g2);
    for (auto &x:ans) {
        for (auto &y:x) {
            cout << y;
            cout << " ";
        }
        cout << endl;
    }
    return 0;
}

